package answer

import "strings"

func openLock(deadends []string, target string) int {
	queue := new(Queue)
	queue.offer("0000")
	result := 0
	tempMap := make(map[string]bool)
	visited := make(map[string]bool)

	for _, str := range deadends {
		tempMap[str] = true
	}
	//遍历队列
	for len(queue.nums) > 0 {
		length := len(queue.nums)
		for length > 0 {
			poll := queue.poll()
			length--
			//判断是否合法
			if ok := tempMap[poll]; ok {
				continue
			}
			//判断是否满足
			if strings.EqualFold(poll, target) {
				return result
			}
			//把相邻节点加入进去
			for i := 0; i < 4; i++ {
				on := minusOn(poll, i)
				if ok := visited[on]; !ok {
					queue.offer(on)
					visited[on] = true
				}
				down := minusDown(poll, i)
				if ok := visited[down]; !ok {
					queue.offer(down)
					visited[down] = true
				}
			}
		}
		result++
	}
	return -1
}

/**
 * @Description: 向上拨动
 * @param s 字符串
 * @param i 拨动位数
 * @return string 结果
 */
func minusOn(s string, i int) string {
	temp := []byte(s)
	if temp[i] == '9' {
		temp[i] = '0'
	} else {
		temp[i] += 1
	}
	return string(temp)
}

/**
 * @Description: 向下拨动
 * @param s 字符串
 * @param i 拨动位数
 * @return string 结果
 */
func minusDown(s string, i int) string {
	temp := []byte(s)
	if temp[i] == '0' {
		temp[i] = '9'
	} else {
		temp[i] -= 1
	}
	return string(temp)
}

type Queue struct {
	nums []string
}

func (q *Queue) offer(s string) {
	if q == nil {
		q.nums = make([]string, 0)
	}
	q.nums = append(q.nums, s)
}

func (q *Queue) poll() (s string) {
	s = q.nums[0]
	q.nums = q.nums[1:]
	return s
}
